def bitonic_sort(arr):
    if len(arr) <= 1:
        return arr
    else:
        first = bitonic_sort([x for x in arr[::2]]) #取偶数
        second = bitonic_sort([x for x in arr[1::2]]) #取奇数
        #print(first)
        #print(second  )
        return bitonic_merge(first + second)

def bitonic_merge(arr):
    if len(arr) == 1:
        return arr
    else:
        print(arr)
        first = bitonic_compare_and_swap(arr, 0, 1, True)
        print(first)
        second = bitonic_compare_and_swap(arr, 2, 3, False)
        return bitonic_merge(first) + bitonic_merge(second)
        #return bitonic_merge(first) 
        #return (first)

def bitonic_compare_and_swap(arr, i, j, is_increasing):   
    if i >= len(arr) or j > len(arr):
        return arr
    if (is_increasing and arr[i] > arr[j]) or (not is_increasing and arr[i] < arr[j]):
        arr[i], arr[j] = arr[j], arr[i]
    return arr

arr = [4, 2, 7, 5, 1, 8, 6, 3]
print(arr)
print(bitonic_sort(arr))